package com.javaDemo.ti;

import java.util.*;

/**
 * 双指针和滑动窗口类算法题详解
 * 
 * @author csy
 * @description 面试中常见的双指针和滑动窗口类算法题的详细解析
 */
public class TwoPointerAndSlidingWindowExamples {

    /**
     * 【双指针类】删除排序数组中的重复项
     * 
     * 问题描述：
     * 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
     * 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
     * 
     * 解题思路详解：
     * 1. 为什么用双指针？
     * - 快指针：探索新的元素
     * - 慢指针：指向最后一个不重复的位置
     * 
     * 2. 详细步骤解析：
     * a) 特殊情况处理
     * - 为什么：处理边界情况
     * - 如何：检查数组是否为空或只有一个元素
     * 
     * b) 双指针初始化
     * - 慢指针(slow)：指向第一个元素
     * - 快指针(fast)：指向第二个元素
     * 
     * c) 遍历过程
     * - 比较fast和slow指向的元素
     * - 不相等时将fast指向的元素复制到slow+1位置
     * 
     * 3. 指针移动策略详解：
     * a) 快指针移动：
     * - 每次都向前移动，寻找新元素
     * b) 慢指针移动：
     * - 只有在发现新元素时才移动
     * 
     * 4. 举例详解：
     * 输入：[1,1,2,2,3,4,4]
     * 过程：
     * - 初始：s=0,f=1: [1],1,2,2,3,4,4
     * - f=1: 遇到1，相同，fast++
     * - f=2: 遇到2，不同，slow++，复制2
     * - f=3: 遇到2，相同，fast++
     * ...
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public static int removeDuplicates(int[] nums) {
        // 处理边界情况：空数组或只有一个元素的数组
        if (nums == null || nums.length == 0)
            return 0;
        if (nums.length == 1)
            return 1;

        // 慢指针，指向当前不重复元素的最后位置
        int slow = 0;

        // 快指针遍历数组，寻找新的不重复元素
        for (int fast = 1; fast < nums.length; fast++) {
            // 当快指针指向的元素与慢指针指向的元素不同时，说明找到了新的不重复元素
            if (nums[fast] != nums[slow]) {
                slow++; // 慢指针向前移动一步
                nums[slow] = nums[fast]; // 将新元素复制到慢指针位置
            }
        }

        return slow + 1; // 返回新数组的长度（慢指针位置+1）
    }

    /**
     * 【滑动窗口类】最小覆盖子串
     * 
     * 问题描述：
     * 给你一个字符串 s 和一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
     * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。
     * 
     * 解题思路详解：
     * 1. 为什么用滑动窗口？
     * - 需要在s中找到包含所有t字符的最小窗口
     * - 窗口大小可变，需要动态调整
     * 
     * 2. 详细步骤解析：
     * a) 初始化数据结构
     * - 目标字符计数器：记录t中每个字符的出现次数
     * - 窗口字符计数器：记录当前窗口中的字符计数
     * 
     * b) 窗口操作
     * - 右指针扩展：寻找可行解
     * - 左指针收缩：优化可行解
     * 
     * c) 匹配过程
     * - 完全匹配：所有t中字符的计数都满足要求
     * - 部分匹配：继续扩展窗口
     * 
     * 3. 优化策略详解：
     * a) 计数器优化
     * - 使用数组代替HashMap提高效率
     * - 使用valid变量记录已匹配字符数
     * 
     * b) 窗口收缩优化
     * - 只在找到可行解时才收缩
     * - 收缩时更新最小长度
     * 
     * 4. 举例详解：
     * 输入：s = "ADOBECODEBANC", t = "ABC"
     * 过程：
     * 1) 扩展窗口直到包含ABC：
     * - ADOBEC (valid)
     * 2) 收缩窗口：
     * - DOBEC (invalid)
     * - 记录ADOBEC
     * 3) 继续扩展：
     * - DOBECODEBA (valid)
     * 4) 收缩：
     * - BANC (valid，更短)
     * 
     * 时间复杂度：O(n)，其中n是字符串s的长度
     * 空间复杂度：O(k)，其中k是字符集大小
     */
    public static String minWindow(String s, String t) {
        // 处理边界情况
        if (s == null || t == null || s.length() < t.length())
            return "";

        // 初始化字符计数数组
        int[] need = new int[128]; // 记录目标字符串t中每个字符需要的数量
        int[] window = new int[128]; // 记录当前窗口中每个字符的数量

        // 统计目标字符串t中每个字符的出现次数
        for (char c : t.toCharArray()) {
            need[c]++;
        }

        // 初始化窗口的左右边界和最小子串的信息
        int left = 0, right = 0;
        int valid = 0; // 已匹配的字符数量
        int start = 0, minLen = Integer.MAX_VALUE;

        while (right < s.length()) {
            char c = s.charAt(right);
            right++; // 扩大窗口

            // 更新窗口内字符的计数
            if (need[c] > 0) {
                window[c]++;
                if (window[c] <= need[c]) {
                    valid++; // 找到一个有效字符
                }
            }

            // 当找到可行解时，尝试通过收缩窗口来优化
            while (valid == t.length()) {
                // 更新最小子串信息
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }

                char d = s.charAt(left);
                left++; // 缩小窗口

                // 更新窗口内字符的计数
                if (need[d] > 0) {
                    if (window[d] <= need[d]) {
                        valid--; // 失去一个有效字符
                    }
                    window[d]--;
                }
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }

    /**
     * 【双指针类】接雨水
     * 
     * 问题描述：
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     * 
     * 解题思路详解：
     * 1. 为什么用双指针？
     * - 每个位置能接的雨水取决于左右两边的最大高度
     * - 双指针可以动态维护左右最大高度
     * 
     * 2. 详细步骤解析：
     * a) 初始化指针
     * - 左指针：数组开始
     * - 右指针：数组结束
     * 
     * b) 维护状态
     * - 左最大高度：从左到当前位置的最大高度
     * - 右最大高度：从右到当前位置的最大高度
     * 
     * c) 计算策略
     * - 选择较小的最大高度决定当前位置能接的水
     * - 移动对应的指针
     * 
     * 3. 指针移动策略：
     * a) 左边最大高度较小时
     * - 可以确定左指针位置能接的水
     * - 移动左指针
     * 
     * b) 右边最大高度较小时
     * - 可以确定右指针位置能接的水
     * - 移动右指针
     * 
     * 4. 举例详解：
     * 输入：[0,1,0,2,1,0,1,3,2,1,2,1]
     * 过程：
     * 1) 初始状态：
     * - leftMax = 0, rightMax = 0
     * - left = 0, right = 11
     * 
     * 2) 第一步：
     * - leftMax = 0 < rightMax = 1
     * - 计算left位置：min(0,1) - 0 = 0
     * - 移动左指针
     * 
     * 3) 继续过程：
     * - 不断更新leftMax和rightMax
     * - 按较小值计算当前位置的水量
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public static int trap(int[] height) {
        if (height == null || height.length < 3)
            return 0;

        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int result = 0;

        while (left < right) {
            // 更新左右最大高度
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);

            // 根据较小的最大高度计算
            if (leftMax < rightMax) {
                result += leftMax - height[left];
                left++;
            } else {
                result += rightMax - height[right];
                right--;
            }
        }

        return result;
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试删除排序数组中的重复项
        System.out.println("=== 删除排序数组中的重复项测试 ===");
        int[] nums1 = { 1, 1, 2, 2, 3, 4, 4 };
        int newLength = removeDuplicates(nums1);
        System.out.println("原数组：" + Arrays.toString(nums1));
        System.out.println("新长度：" + newLength);
        System.out.println("处理后的有效部分：" + Arrays.toString(Arrays.copyOf(nums1, newLength)) + "\n");

        // 测试最小覆盖子串
        System.out.println("=== 最小覆盖子串测试 ===");
        String s = "ADOBECODEBANC", t = "ABC";
        System.out.println("字符串s：" + s);
        System.out.println("字符串t：" + t);
        System.out.println("最小覆盖子串：" + minWindow(s, t) + "\n");

        // 测试接雨水
        System.out.println("=== 接雨水测试 ===");
        int[] height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
        System.out.println("输入数组：" + Arrays.toString(height));
        System.out.println("可以接的雨水量：" + trap(height));
    }
}